\documentclass{beamer}
\usepackage[T2A]{fontenc}
\usepackage[utf8]{inputenc}
\usepackage[english,russian]{babel}
\usepackage{amssymb,amsfonts,amsmath,mathtext}
\usepackage{cite,enumerate,float,indentfirst}
\usepackage{graphicx}
\usepackage{xcolor}
%\usetheme{CambridgeUS}
\usepackage{listings}
\usecolortheme{beaver}
%\usetheme{Szeged}

\usepackage{listings}
\lstset{
  language=C, extendedchars=\true
}

\title{Наглядный материал по курсу \\ \textbf{Программно-алгоритмическое обеспечение АИУС}}
\author{Кондрашов К. С.}
\date{2013}
\graphicspath{{images/}}
\DeclareGraphicsExtensions{.png,.pdf}

\begin{document}
\maketitle

\begin{frame}
\begin{center}
\frametitle{...}
\textbf{TODO: добавить по мере надобности}
\end{center}
\end{frame}

\begin{frame}
\begin{center}
\frametitle{Особенности отладки для встраиваемых систем}
\begin{itemize}
\itemудаленная отладка через pdebug на target + gdb на host
\itemиспользование qconn для файлового обена и просмотра файловой системы
\itemвозможность использования RS-232
\end{itemize}
\begin{figure}[h]
\center{\includegraphics[width=1.\linewidth]{debug}}
\label{ris:debug}
\end{figure}
\end{center}
\end{frame}

\begin{frame}
\frametitle{Модуль 2}
\begin{center}
\Large{
  Принципы построения программно-алгоритмического 
  обеспечения вычислительных средств АИУС
}
\end{center}
\end{frame}

\begin{frame}
\begin{center}
\frametitle{Простейшие варианты архитектуры ПО встраиваемых систем}
\begin{itemize}
\item{Пример применения бесконечного цикла опроса в качестве основного элемента архитектуры встраиваемой системы}
\item{Пример применения цикла, ожидающего наступления сообщений}
\item{Пример организации работы встраиваемой системы на основе обработки прерываний}
\item{Пример встраиваемой системы на основе обработки очереди сообщений}
\end{itemize}
\end{center}
\end{frame}

\begin{frame}
\begin{center}
\frametitle{Пример применения бесконечного цикла опроса}
\begin{figure}[h]
\center{\includegraphics[height=0.75\linewidth]{inf_loop}}
\label{ris:inf_loop}
\end{figure}
\end{center}
\end{frame}

\begin{frame}[fragile]
\frametitle{Пример применения бесконечного цикла опроса}
\begin{scriptsize}
\begin{lstlisting}
// main.c
// #include ...
#include "hpi.h"
int main(int argn, char* argv[])
{
  if (init_hpi() < 0) {
    LOG_Printf("Cannot initialize HPI");
    exit(EXIT_ERROR);
  }
  while(1) {
    switch(hpi_change_status()) {
      case eChanged:
        process_data(); break;
      case eUnknown:
        LOG_Printf("Error in getting status"); break;
      default:
        sleep(TIME_INTERVAL);
    }
  }
  exit(EXIT_SUCCESS);
}
\end{lstlisting}
\end{scriptsize}
\end{frame}

\begin{frame}[fragile]
\frametitle{Пример применения бесконечного цикла опроса}
\begin{scriptsize}
\begin{lstlisting}
// data_processor.h
#ifndef HPI_H__
#define HPI_H__
#include "status.h"
init_status_t   init_hpi(void);
update_status_t hpi_change_status(void);
// ...
#endif // HPI_H__
\end{lstlisting}

\begin{lstlisting}
// status.h
#ifndef STATUS_H__
#define STATUS_H__
// ... 
typedef enum update_status_t_ {
  eUnchanged, // 0
  eChanged,   // 1
  eUnknown    // ... 
} update_status_t;
typedef enum init_status_t_ {
  eSuccess,
  eError
} init_status_t;
// ...
\end{lstlisting}
\end{scriptsize}
\end{frame}

\begin{frame}
\begin{center}
\frametitle{Пример ожидания события}
\begin{figure}[h]
\center{\includegraphics[height=0.8\linewidth]{event_wait}}
\label{ris:event_wait}
\end{figure}
\end{center}
\end{frame}

\begin{frame}[fragile]
\frametitle{Пример ожидания события}
\begin{scriptsize}
\begin{lstlisting}
// main.c
// #include ...
#include "events.h"
#include "process_event.h"
int main(int argn, char* argv[])
{
  // ... 
  event_t event;
  while(1) {
    if (check_new_event(&event)) // blocking call
      switch(event.source)
      {
        case eHPI:
          process_hpi_event(&event); break;
        case eGPIO:
          process_gpio_event(&event); break;
        default:
          LOG_Printf("Unknown event source %d", event.source);
      }
  }
  exit(EXIT_SUCCESS);
}
\end{lstlisting}
\end{scriptsize}
\end{frame}

\begin{frame}[fragile]
\frametitle{Пример ожидания события}
\begin{scriptsize}
\begin{lstlisting}
// events.h
#ifndef EVENTS_H__
#define EVENTS_H__
#include "status.h"
typedef struct event_t_ {
  unsigned char source;
  char* data;
} event_t;
enum event_source {
  eHPI,
  eGPIO
};
update_status_t check_new_event(&event)
#endif 
\end{lstlisting}
\begin{lstlisting}
// process_events.h
#ifndef PROCESS_EVENT_H__
#define PROCESS_EVENT_H__
#include "event.h"
void process_hpi_event(const event_t*);
void process_gpio_event(const event_t*);
#endif 
\end{lstlisting}
\end{scriptsize}
\end{frame}

\begin{frame}
\begin{center}
\frametitle{Пример обработки прерываний}
\begin{figure}[h]
\center{\includegraphics[height=0.8\linewidth]{inter}}
\label{ris:inter}
\end{figure}
\end{center}
\end{frame}

\begin{frame}[fragile]
\frametitle{Пример обработки прерываний}
\begin{scriptsize}
\begin{lstlisting}
// main.c
#include "irq.h"
#include "handlers.h"
int main(int argn, char* argv[])
{
  enable_interrupts(IRQ1 | IRQ2);
  set_interrupt(IRQ1, hpi_handler);
  set_interrupt(IRQ2, rs232_handler);
  while(1) {
    sleep(10);
  }
  exit(EXIT_SUCCESS);
}
\end{lstlisting}
\begin{lstlisting}
// irq.h
#ifndef IRQ_H__
#define IRQ_H__
void enable_iterrupts(unsigned char);
void set_interrupt(unsigned char, void (*)(void));
#endif
\end{lstlisting}
\end{scriptsize}
\end{frame}

\begin{frame}[fragile]
\frametitle{Пример обработки прерываний}
\begin{scriptsize}
\begin{lstlisting}
// handlers.h
#ifndef HANDLERS_H__
#define HANDLERS_H__
void hpi_handler(void);
void rs232_handler(void);
#endif HANDLERS_H__
\end{lstlisting}
\begin{lstlisting}
// handlers.c
// ...
#include "rs232.h"
#include "hpi.h"
interrupt void hpi_handler(void) {
  if (g_hpi_data.reg_wr & eHPI_NewData) { 
    // ...
  }
  // ...
}
void rs232_handler(void) {
  // ...
}
\end{lstlisting}
\end{scriptsize}
\end{frame}

\begin{frame}[fragile]
\frametitle{Пример обработки прерываний}
\begin{scriptsize}
\begin{lstlisting}
// handlers.h
#ifndef HANDLERS_H__
#define HANDLERS_H__
void hpi_handler(void);
void rs232_handler(void);
#endif HANDLERS_H__
\end{lstlisting}
\begin{lstlisting}
// handlers.c
// ...
#include "rs232.h"
#include "hpi.h"
void hpi_handler(void) {
  if (g_hpi_data.reg_wr && eHPI_NewData) { 
    // ...
  }
  // ...
}
void rs232_handler(void) {
  // ...
}
\end{lstlisting}
\end{scriptsize}
\end{frame}

\begin{frame}
\begin{center}
\frametitle{Пример очереди сообщений}
\begin{figure}[h]
\center{\includegraphics[height=0.8\linewidth]{msg_queue}}
\label{ris:msg_queue}
\end{figure}
\end{center}
\end{frame}

\begin{frame}[fragile]
\frametitle{Пример очереди сообщений}
\begin{scriptsize}
\begin{lstlisting}
// main.c
// ...
#include "msg.h"
#include "int.h"

int main(int argn, char* argc[])
{
  msg_t msg;
  if (init_msg_queue() != eSuccess) {
    LOG_Printf("Cannot init msg queue");
    exit(EXIT_FAILURE);
  }
  enable_interrupts(IRQ1);
  set_interrupt(IRQ1, hpi_handler);
  while(1) {
    get_from_queue(&msg);
    process_data(&msg);
  }
  exit(EXIT_SUCCESS);
}
\end{lstlisting}
\end{scriptsize}
\end{frame}

\begin{frame}[fragile]
\frametitle{Пример очереди сообщений}
\begin{scriptsize}
\begin{lstlisting}
// msg.h
#ifndef MSG_H__
#define MSG_H__
// ...
typedef struct msg_t_ {
  int num;
  double val;
} msg_t;
status_result_t init_msg_queue(void);
status_result_t put_into_queue(msg_t msg);
status_result_t get_from_queue(msg_t* msg);
#endif
\end{lstlisting}
\begin{lstlisting}
// int.h
#ifndef INT_H__
#define INT_H__
// enable_interrupts; set_interrupts;
void hpi_handler(void);
#endif
\end{lstlisting}
\end{scriptsize}
\end{frame}

\begin{frame}[fragile]
\frametitle{Пример очереди сообщений}
\begin{scriptsize}
\begin{lstlisting}
// int.c
#include "int.h"
#include "msg.h"
#include "hpi.h"
// ...
void hpi_handler(void)
{
  msg_t msg = {0};
  unsigned i, data_size = MAX_DATA_SIZE;
  if (g_hpi_data.reg_wr & eHPI_NewData) { 
    data_size = 
      (g_hpi_data.data_size < MAX_DATA_SIZE) 
      ? g_hpi_data : MAX_DATA_SIZE;
    for (i = 0; i < data_size; ++i)
    {
      msg.num = i;
      msg.data = *(g_hpi_data.data + i * sizeof(msg.data));
      put_into_queue(msg);
    }
  }
}
\end{lstlisting}
\end{scriptsize}
\end{frame}

\begin{frame}[fragile]
\frametitle{Пример очереди сообщений}
\begin{scriptsize}
\begin{lstlisting}
// msg.c
#include "msg.h"
#include <rtems.h>
// ...
static rtems_id s_queue_id = {0};
status_result_t get_from_queue(msg_t* msg) {
  unsigned size;
  rtems_interval timeout = {0};
  rtems_message_queue_receive(
      s_queue_id, pack, &size, 
      RTEMS_NO_WAIT | RTEMS_NO_TIMEOUT, timeout);
  return (size == sizeof(*pack)) ? eSuccess : eFailure;
}
status_result_t put_into_queue(msg_t msg) {
  // ... 
}
status_init_t init_msg_queue(void) {
  rtems_status_code status;
  rtems_name in_queue_name = rtems_build_name('I','M','P','Q');
  status = rtems_message_queue_create(in_queue_name, 10,
      sizeof(msg_t), RTEMS_FIFO | RTEMS_LOCAL, &s_queue_id);
  return (status_init_t)status;
}
\end{lstlisting}
\end{scriptsize}
\end{frame}

\begin{frame}
\frametitle{Особенности сложных систем}
\begin{itemize}
\itemналичие как синхронных, так и асинхронных событий
\itemбольшое количество источников прерываний
\itemналичие параллельных вычислительных алгоритмов
\itemбольшое количество программных объектов и связей между ними
\itemнеобходимость синхронизации совместного доступа
\end{itemize}
\textbf{Как следствие -- сложность применения одной из перечисленных архитектур напрямую}
\end{frame}

\begin{frame}
\begin{center}
\frametitle{Сервисная многопоточная программа}
\begin{figure}[h]
\center{\includegraphics[width=1.0\linewidth]{difficult_sys}}
\label{ris:difficult_sys}
\end{figure}
\end{center}
\end{frame}

\begin{frame}
\frametitle{ОСРВ -- инструмент для конструирования системы реального времени}
\begin{itemize}
\item{API} для создание параллельных задач с приоритетами
\itemобработка прерываний (возможно, с приоритетами) с вызовом назначенного обработчика
\itemобработка событий с вызовом назначенного обработчика
\itemобработка исключений
\itemорганизация обмена между параллельными задачами: сообщения, мутексы, семафоры, мониторы
\end{itemize}
В отличие от простейших архитектур, применение указанных технологий совместно не требует от разработчика кодирования <<вручную>> и использования ассемблера
\end{frame}

\begin{frame}
\frametitle{Режимы <<активизации>> параллельных задач}
\begin{itemize}
\itemПериодические задачи (управляемые системным таймером), monotonic tasks

Активируются ядром в определенные моменты времени:
\begin{figure}[h]
\center{\includegraphics[height=0.3\linewidth]{tasks}}
\label{ris:tasks}
\end{figure}

\itemАпериодические задачи (управляемые событиями):

Активизируются по наступлению события (прерывания и проч.)

\center{\begin{picture}(80, 30)
\put(0,15){\textbf{event}}
\put(30,17){\vector(1,0){20}}
\put(50,15){<process>}
\end{picture}}

\end{itemize}
\end{frame}

\begin{frame}
\frametitle{Поддержка периодических задач в ОС}
\begin{figure}[h]
\center{\includegraphics[height=0.6\linewidth]{os_periodic}}
\label{ris:os_periodic}
\end{figure}
\end{frame}

\begin{frame}[fragile]
\frametitle{Поддержка периодических задач в ОС}
\begin{scriptsize}
\begin{lstlisting}
rtems_task supervisor_task(rtems_task_argument unused)
{
  rtems_name name = {0};
  rtems_id period = 0;
  rtems_status_code status = RTEMS_SUCCESSFUL;
  name = rtems_build_name('P', 'R', 'D', 'S');
  status = rtems_rate_monotonic_create(name, &period);
  if (status != RTEMS_SUCCESSFUL) {
    exit(EXIT_FAILURE);
  }
  while (1) {
    if (rtems_rate_monotonic_period(period, SUPERVISOR_PERIOD) == 
        RTEMS_TIMEOUT) {
      exit(EXIT_FAILURE);
    }
    // process data
  }
  status = rtems_rate_monotonic_delete(period);
  if (status != RTEMS_SUCCESSFUL) {
    exit(EXIT_FAILURE);
  }
  status = rtems_task_delete(RTEMS_SELF); 
}
\end{lstlisting}
\end{scriptsize}
\end{frame}

\begin{frame}
\frametitle{Диаграмма состояний задачи}
\begin{figure}[h]
\center{\includegraphics[height=0.7\linewidth]{idle}}
\label{ris:idle}
\end{figure}
\end{frame}

\begin{frame}
\frametitle{Состояние SLEEP}
\begin{figure}[h]
\center{\includegraphics[width=1.\linewidth]{sleep}}
\label{ris:sleep}
\end{figure}
\end{frame}

\begin{frame}
\frametitle{Временная структура периодических задач}
\center{\begin{itemize}
\item{$S_i$ -- начало i-ой задачи}
\item{$C_i$ -- время выполнения i-ой задачи}
\item{$T_i$ -- период i-ой задачи}
\item{$D_i$ -- относительный дедлайн i-ой задачи}
\end{itemize}}
\begin{figure}[h]
\center{\includegraphics[height=.5\linewidth]{per_model}}
\label{ris:per_model}
\end{figure}
\end{frame}

\begin{frame}
\frametitle{Планирование периодических задач}
\textbf{Дано:} 

n периодических задач: $\left\{\tau_1, \tau_2, \cdots, \tau_n\right\}$ : 
$\tau_i\left(C_i, T_i, D_i\right)$

\textbf{Цель:}
\begin{itemize}
\item{Выполнять каждую задач в пределах ее дедлайна $D_i$}
\item{Проверять осуществимость перед запуском}
\end{itemize}

\textbf{Условия:}
\begin{itemize}
\itemЗадачи выполняются на одном процессоре
\itemЗадачи независимы (не блокируют друг друга)
\itemЗадачи синхронны ($\forall{(i,j)} S_i = S_j = 0$)
\itemОтносительные дедлайны равны периодам ($D_i = T_i$)
\end{itemize}
\end{frame}

\begin{frame}
\frametitle{<<Жесткое>> планирование (timeline scheduling)}
\textbf{Процедура:}
\begin{itemize}
\itemОсь времени делится на интервалы равной длины (кванты по времени, time slots)
\itemКаждая задача статически размещается в квантах, с целью удовлетворения локального
и абсолютного дедлайна
\itemЗапуск каждого кванта осуществляется таймером
\end{itemize}
\textbf{Преимущества:}
\begin{itemize}
\itemПростая реализация (не нужна ОСРВ)
\itemНизкие накладные расходы (нет <<лишних>> задач)
\itemПрямой контроль джиттера
\end{itemize}
\textbf{Недостатки:}
\begin{itemize}
\itemНеустойчива к превышению времени выполнения
\itemПлохо масштабируема
\itemСложно обрабатывать апериодические задачи
\end{itemize}
\end{frame}

\begin{frame}
\frametitle{Пример <<жесткого>> планирования}
\center{\begin{itemize}
\item{D -- второстепенный временной квант}
\item{T -- главный временной квант}
\end{itemize}}
\begin{figure}[h]
\center{\includegraphics[height=.6\linewidth]{hard_schedule}}
\end{figure}
\end{frame}

\begin{frame}
\frametitle{Пример <<жесткого>> планирования: реализация}
\begin{figure}[h]
\center{\includegraphics[height=.7\linewidth]{hard_schedule_impl}}
\end{figure}
\end{frame}

\begin{frame}
\frametitle{Проблемы превышения времени выполнения задачи}
Что следует делать, если задача <<не укладывается>> в отведенный
ей второстепенный временной квант?
\begin{enumerate}
\itemПозволить задаче выполняться

Как следствие -- \textit{эффект домино} -- все остальные задачи
также выйдут из заданных для них временных пределов

\itemПрервать задачу

Как следствие -- система остается в неопределенном состоянии
\end{enumerate}

\textbf{Серьезный недостаток системы с <<жестким>> планированием}
\end{frame}

\begin{frame}
\frametitle{Масштабирование задач}
Если одну (или несколько) задач требуется обновить, что может 
привести к увеличению времени ее работы, требуется произвести
пересчет всей схемы планирования в целом.

Например: задача B обновляется, при этом $C_A + C_B > D$

В этом случае задача B разбивается на задачи $(B_1, B_2)$:
\begin{figure}[h]
\center{\includegraphics[height=.4\linewidth]{extand}}
\end{figure}
\end{frame}

\begin{frame}
\frametitle{Масштабирование задач}
Изменение \textbf{частоты запуска} некоторой задачи может иметь
эффект еще более значительный:
\begin{figure}
\center{\includegraphics[height=.3\linewidth]{extand1}}
\end{figure}
D = 25, T = 100 -- было; 
D = 5, T = 200 -- стало
\begin{figure}[h]
\center{\includegraphics[height=.3\linewidth]{extand2}}
\end{figure}
\end{frame}

\begin{frame}
\frametitle{Планирование с использованием приоритетов}
\textbf{Процедура:}
\begin{itemize}
\itemКаждой задаче назначается приоритет на основе ее временных
ограничений
\itemПроизводится проверка осуществимости данной схемы планирования
на основе математических расчетов
\itemЗадачи выполняются с использованием ядра, поддерживающего
потоки (нити) с приоритетами
\end{itemize}
\textbf{Назначение приоритетов:}
\begin{itemize}
\itemВ соответствии с периодом: Rate Monotonic (RM):
$$
p_i = \frac{1}{T_i}
$$
назначаются статически
\itemВ соответствии с дедлайном: Earliest Deadline First (EDF):
$$
p_i = \frac{1}{d_i}; d_{i,k} = r_{i,k} + D_i
$$
\end{itemize}
\end{frame}

\begin{frame}
\frametitle{Осуществимость алгоритма планирования}
\begin{itemize}
\itemКаждая задача задействует процессор на промежуток времени $U_i = \frac{C_i}{T_i}$
\itemТаким образом, полное время использования процессора (utilization): 
$U_p = \sum\limits_{i=1}^{n}{\frac{C_i}{T_i}}$
\item$U_p$ характеризует \textit{загрузку процессора}

\end{itemize}
\begin{figure}[h]
\center{\includegraphics[height=.3\linewidth]{rm}}
\end{figure}

\textbf{Необходимое условие:}

Если $U_p > 1$, процессор считается перегруженным, а набор задач
$\{\tau_1, \tau_2, \cdots, \tau_n\}$ не может быть спланирован.
\end{frame}

\begin{frame}
\frametitle{Особенности RM-планирования}
\begin{itemize}
\itemНарушение дедлайна одной из задач
$$
U_p = \frac{3}{6} + \frac{4}{9} = 0.944
$$
\begin{figure}[h]
\center{\includegraphics[height=.2\linewidth]{rm_unf}}
\end{figure}
\itemВерхний предел загрузки процессора
$$
U_p = \frac{3}{6} + \frac{3}{9} = 0.833
$$
\begin{figure}[h]
\center{\includegraphics[height=.2\linewidth]{rm_ub}}
\end{figure}
Увеличение $C_1$ или $C_2$ делает набор задач непланируемым
\end{itemize}
\end{frame}

\begin{frame}
\frametitle{Особенности RM-планирования}
\begin{itemize}
\itemДругой верхний предел загрузки процессора
$$
U_p = \frac{2}{4} + \frac{4}{8} = 1
$$
\begin{figure}[h]
\center{\includegraphics[height=.2\linewidth]{rm_up1}}
\end{figure}
Верхний предел зависит от набора задач
\itemНаименьший верхний предел загрузки процессора (least
upper bound) для разных параметров множества из $n$ задач:
\begin{figure}[h]
\center{\includegraphics[height=.2\linewidth]{less_ub}}
\end{figure}
\end{itemize}
\end{frame}

\begin{frame}
\frametitle{Достаточное условие планируемости RM-алгоритмом}
\begin{itemize}
\itemСуществует такой предел $U_{lub}$, что если 
$$
U_p \le U_{lub},
$$
где $U_p$ -- суммарная загрузка (utilization) процессора,
$$
\left\{\tau_1, \cdots, \tau_n\right\},
$$
то данный набор задач гарантированно \textbf{планируем RM-
алгоритмом}
\itemЕсли $U_{lub} < U_p \le 1$, о осуществимости планирования
нельзя сказать ничего однозначного.
\end{itemize}
\end{frame}

\begin{frame}
\frametitle{Основные результаты}
\begin{itemize}
\item
\begin{math}
\textit{Условия:}
\left\{
\begin{array}{l}
\textit{Независимые задачи} \\
S_i = 0; D_i = T_i
\end{array}
\right\}
\end{math}

\item\textit{Liu , Layland 1973} -- теорема о возможности планирования
набора из $n$ периодических задач:
\begin{enumerate}
\item\textit{при помощи RM-алгоритма: если} 
$$
\sum\limits_{i=1}^n{\frac{C_i}{T_i}} \le n\left(2^{1/n} - 1\right)
$$
\item\textit{при помощи EDF-алгоритма: тогда и только тогда, когда}
$$
\sum\limits_{i=1}^{n} {\frac{C_i}{T_i}}\le 1
$$
\end{enumerate}
\itemДля RM-алгоритма $n \to \infty$, $U_{lub} \to \ln(2)$

\end{itemize}
\end{frame}

\begin{frame}
\frametitle{Особый случай}
Если задачи имеют \textit{гармонический} период, то $U_{lub} = 1$.
$$
U_p = \frac{2}{4} + \frac{4}{8} = 1
$$
\begin{figure}[h]
\center{\includegraphics[width=1.\linewidth]{harm}}
\end{figure}
\end{frame}

\begin{frame}
\frametitle{Допустимые области планирования: пример}
\begin{figure}[h]
\center{\includegraphics[width=1.\linewidth]{sched_reg1}}
\end{figure}
\end{frame}

\begin{frame}
\frametitle{Допустимые области планирования: пример}
\begin{figure}[h]
\center{\includegraphics[width=1.\linewidth]{sched_reg2}}
\end{figure}
\end{frame}

\begin{frame}
\frametitle{Оптимальность RM-алгоритма}
\begin{itemize}
\itemАлгоритм с RM-планированием является оптимальным
\textbf{с точки зрения осуществимости} среди алгоритмов
со статическим назначением приоритетов:
\itemЕсли существует возможность назначить приоритеты для
набора задач $T = \left\{\tau_1, \cdots, \tau_n\right\}$,
так, чтобы планирование было осуществимо, то RM-планирование
осуществимо для данного $T$.
\itemЕсли $T$ невозможно спланировать RM-алгоритмом, то 
невозможно и никаким другим со статическим назначением 
приоритетов.
\end{itemize}
\end{frame}

\begin{frame}
\frametitle{Оптимальность EDF-алгоритма}
\begin{itemize}
\item{EDF}-алгоритм является оптимальным с точки зрения
осуществимости среди \textbf{всех} алгоритмов:
\itemЕсли есть осуществимое планирование для набора $T$
задач, то его возможно сделать с помощью EDF-алгоритма.
\itemЕсли $T$ невозможно спланировать EDF-алгоритмом, то никаким
другим тоже.
\end{itemize}
\end{frame}

\begin{frame}
\frametitle{Разделение ресурсов между задачами}
Механизмы разделения ресурсов:
\begin{itemize}
\itemОбщие области памяти
\itemОбмен сообщениями
\itemАсинхронные буферы
\end{itemize}
Используемые примитивы нижнего уровня:
\begin{itemize}
\itemСемафоры
\itemМутексы
\itemМониторы
\itemи проч. в зависимости от платформы.
\end{itemize}
\end{frame}

\begin{frame}
\frametitle{Использование критических секций (Critical sections, CS)}
Ниже -- пример использования семафора $s$ для одновременного доступа
к общим переменным. Перед началом использования ожидаем семафор (wait), 
после использования -- отпускаем (signal).
\begin{figure}[h]
\center{\includegraphics[width=.7\paperheight]{cs}}
\end{figure}
\end{frame}

\begin{frame}
\frametitle{Блокирование на семафоре}
\begin{figure}[h]
\center{\includegraphics[width=.7\paperheight]{sem}}
\end{figure}
p -- приоритет,
D -- длина критической секции.

Кажется, что максимальное время блокирования задачи 1 равно длине
критической секции задачи 2, однако это не так... (см. далее).
\end{frame}

\begin{frame}
\frametitle{Инверсия приоритетов}
\begin{figure}[h]
\center{\includegraphics[width=1.\linewidth]{prio_inv}}
\end{figure}
\begin{scriptsize}
Задача 1 имеет наибольший приоритет, задача 3 -- наименьший. Задача 3
получает ресурс, входит в критическую секцию. Она вытесняется задачей 1,
которая потом пытается получить ресурс и блокируется. Задача 2 вытесняет
задачу 3 в момент времени 4, оставляя задачу 1 заблокированной. В результате
задача 2 (приоритет ниже) блокирует задачу 1 (приоритет выше).
\end{scriptsize}
\end{frame}

\begin{frame}
\frametitle{Протоколы доступа к ресурсам}
Проектируются так, чтобы избежать инверсии приоритетов.
\begin{enumerate}
  \item С использованием статического назначения приоритетов:
    \begin{itemize}
      \itemНаследование приоритетов (Priority Inheritance Protocol, PIP)
      \itemОграничение приоритета (Priority Ceiling Protocol, PCP)
      \itemНевытесняемый (Non Preemptive Prototol, NPP)
      \itemЛокер (locker) с наивысшим приоритетом (Highest Locker Priority, HLP)
    \end{itemize}
  \itemС использованием EDF:
    \begin{itemize}
      \itemПолитика стека ресурсов (Stack Resource Policy, SRP)
    \end{itemize}
\end{enumerate}
\end{frame}

\begin{frame}
\frametitle{Наследование приоритетов (Priority Inheritance Protocol, PIP)}
[Sha, Rajkumar, Lehosczy 1990].
Если задача 1 блокируется, пытаясь получить ресурс, то задача 2, обладающая
данным ресурсом получает приоритет задачи 1.
\begin{figure}[h]
\center{\includegraphics[width=1.\linewidth]{pip}}
\end{figure}
\end{frame}

\begin{frame}
\frametitle{Особенности PIP}
\textbf{Виды блокировки в PIP:}
\begin{itemize}
\itemПрямая блокировка: задача блокируется на ресурсе.
\itemКосвенная блокирова задача заблокирована, поскольку задача с меньшим
приоритетом завладела высшим приоритетом.
\end{itemize}
\textbf{Достоинства:}
\begin{itemize}
\itemПрозрачен для программиста
\itemРешает задачу инверсии приоритетов
\end{itemize}

\textbf{Недостатки:}
\begin{itemize}
\itemНе позволяет избежать дедлоков (deadlocks) и цепных блокировок
(chained locking).
\end{itemize}
\end{frame}

\begin{frame}
\frametitle{Демонстрация дедлока в PIP}
\begin{figure}[h]
\center{\includegraphics[height=.4\paperheight]{pip_deadlock}}
\end{figure}
\begin{scriptsize}
Задача 1 имеет более высокий приоритет. В момент 1 задача 2 захватывает
ресурс a. В момент 2 задача 1 вытесняет задачу 2, и в момент 3 захватывает b.
Обладая ресурсом b, она пытается захватить ресурс a, который захвачен задачей
2, задача 1 блокируется. В момент 4 Задача 2 должна продолжить выполняться. 
В момент 5 она пытается захватить ресурс b, который захвачен задачей 1.
\textbf{В итоге -- дедлок}
\end{scriptsize}
\end{frame}

\begin{frame}
\frametitle{Цепная блокировка в PIP}
\center{\includegraphics[width=\linewidth]{pip_chainlock}}

Можно показать, что \textbf{$\tau_i$ может быть заблокирован как минимум
один раз любой задачей с низшим приоритетом}
\end{frame}

\begin{frame}
\frametitle{Протокол с ограничением приоритета (PCP)}
\begin{itemize}
  \item Может быть описан как PIP с тестом доступа.
  \item Задача может войти в критическую секцию только тогда, когда она
  не принадлежит другой задаче, и нет опасности цепной блокировки.
\end{itemize}
Для избежания цепной блокировки задача может остановиться при входе
в критическую секцию (блокировка по ограничению приоритета).
\begin{itemize}
  \item Каждому семафору $s_k$ назначается ограничение (ceiling):
  $$
    C(s_k) = max\{P_j:\tau_j~\textit{использует}~s_k\}
  $$
  \item Задача $\tau_j$ может войти в критическую секцию, только если
  $$
    P_j > max\{C(s_k):s_k~\textit{захвачен задачей}~\ne \tau_j\}
  $$
\end{itemize}
\end{frame}

\begin{frame}
\frametitle{Протокол с ограничением приоритета (PCP)}
\center{\includegraphics[width=\linewidth]{pcp}}
В момент $t_1$ задача $\tau_2$ блокируется механизмом PCP, поскольку
$P_2 < C(s_1)$.
\end{frame}

\begin{frame}
\frametitle{Протокол с ограничением приоритета (PCP)}
{\Large
\textbf{Основные свойства:}
  \begin{enumerate}
    \item Теорема 1: 
      При использовании PCP каждая задача может быть заблокирована
      лишь однажды. 
    \item Теорема 2: 
      PCP предотвращает цепную блокировку. 
    \item Теорема 3:
      PCP предотвращает дедлоки.
  \end{enumerate}
}
\end{frame}

\begin{frame}
\frametitle{Протокол с ограничением приоритета (PCP)}
{\Large
  \textbf{Преимущества:}
  \begin{enumerate}
    \item Блокирование сводится \textbf{только к одной} критической
      секции.
    \item Предотвращает дедлоки.
  \end{enumerate}
  \textbf{Недостатки:}
  \begin{enumerate}
    \item Непрозрачно для программиста: семафоры требуют использования
      ограничителей (ceiling).
  \end{enumerate}
}
\end{frame}

\begin{frame}
\frametitle{Типичный дедлок}
\center{\includegraphics[width=\linewidth]{typical_deadlock}}
\end{frame}

\begin{frame}
\frametitle{Устранение дедлока при помощи PCP}
\center{\includegraphics[width=\linewidth]{pcp_vs_deadlock}}
\end{frame}

\begin{frame}
\frametitle{Не вытесняющий протокол (NPP)}
{\Large
  \begin{enumerate}
    \item Вытеснение запрещается в критических секциях
    \item Реализация: когда задача входит в критическую секцию,
      ее приоритет повышается до максимального.
  \end{enumerate}
  \begin{itemize}
    \item \textbf{Преимущества:} простота
    \item \textbf{Недостатки:} задачи с высоким приоритетом, не входящие
      в критическую секцию, также блокируются.
  \end{itemize}
}
\end{frame}

\begin{frame}
\frametitle{Конфликт в критической секции}
\center{\includegraphics[width=\linewidth]{cs_conflict}}
\end{frame}

\begin{frame}
\frametitle{Диспетчеризация при помощи NPP}
\center{\includegraphics[width=\linewidth]{npp}}
{\Large
$$
  P_{cs} = max\{P_1, \cdots, P_n\}
$$
}
\end{frame}

\begin{frame}
\frametitle{Проблемы NPP}
\center{
  \includegraphics[width=\linewidth]{npp_problems}

  {\Large
  $\tau_1$ не может вытеснить другие, хотя могла бы
  }
}
\end{frame}

\begin{frame}
\frametitle{Локер с высшим приоритетом (HLP)}
{\Large
  \textbf{Принцип:}

  Задача в критической секции получает наибольший возможный
  приоритет.

  \textbf{Особенности:}
  \begin{enumerate}
    \item Простая реализация
    \item Задача блокируется, когда пытается вытеснить другую,
    а не когда входит в критическую секцию
  \end{enumerate}
}
\end{frame}

\begin{frame}
\frametitle{Диспетчеризация с помощью HLP}
\center{\includegraphics[width=\linewidth]{hlp}}
{\Large
  $$
    P_{CS} = max\{P_k|\tau_k~\textit{использует}~CS\}
  $$
$\tau_2$ блокируется, но $\tau_1$ может вытеснять внутри 
критической секции.
}
\end{frame}

\begin{frame}
\frametitle{Проблемы HLP}
\center{\includegraphics[width=\linewidth]{hlp_problems}}
$\tau_1$ блокируется только при выполнении условия $test$,
которое может измениться вследствии блокирования задачей
с низшим приоритетом $\tau_2$.
\end{frame}

\begin{frame}
\frametitle{В итоге}
{\Large
  \begin{enumerate}
  \item Производим выбор синхронизирующего алгоритма
    и протокола доступа к ресурсам.
  \item Вычисляем максимальное время блокирования для
    каждой из задач $B_i$.
  \item Рассчитываем тест возможности диспетчеризации
    с блокировочными ограничениями.
  \end{enumerate}
}
\end{frame}

\begin{frame}
\frametitle{LL-тест}
{\Large
Применяется для $D = T$
}
\center{\includegraphics[width=\linewidth]{rm_ll}}
{\Large
Условие возможности диспетчеризации:
$$
  \forall{i}
  \sum\limits_{k = 1}^{i - 1} {\frac{C_k}{T_k}} +
  \frac{C_i + B_i}{T_i} \le
  i\left(2^{1/i} - 1\right)
$$
}
\end{frame}

\begin{frame}
\frametitle{RTA-тест}
{\Large
Применяется для $D \le T$
}
\center{\includegraphics[width=\linewidth]{rm_ll}}
{\Large
Условие возможности диспетчеризации: $\forall{i}~R_i \le D_i$:
$$
  R_i = C_i + B_i +
  \sum\limits_{k = 1}^{i - 1}
  {\left(\frac{R_i}{T_k}\right)C_k}
$$
}
\end{frame}

\begin{frame}
\frametitle{Разделение ресурсов с использованием EDF}
{\Large
  Рассмотренные протоколы разрабатывались для планирования
  со статическим назначением приоритетов. Однако:
}

\begin{itemize}
  \item NPP также может быть использован для EDF
  \item PIP был модифицирован для использования с EDF [Spuri, 1997]
  \item PCP был модифицирован для исплоьзованим с EDF [Chen-Li, 1990]
  \item Существует протокол доступа к ресурсам, работающий как с RM,
    так и с EDF [Baker, 1990]
\end{itemize}
\end{frame}

\begin{frame}
\frametitle{Задачи и стек}
{\Large
  Каждая задача обычно использует отдельный стек для:
  \begin{itemize}
    \item хранения значения в регистрах (контекста)
    \item передачи значений в функции
    \item хранения локальных переменных
  \end{itemize}
}
\center{\includegraphics[height=.5\paperheight]{stack}}
\end{frame}

\begin{frame}
\frametitle{Задачи и стек}
{\Large
  Как правило, стек нельзя разделять между задачами:
}
\center{\includegraphics[width=\linewidth]{stack_sharing}}
\end{frame}

\begin{frame}
\frametitle{Диспетчеризация в QNX}
\large{
  \textbf{Правила диспетчеризации (одно вычислительное ядро):}
    \begin{itemize}
      \item только один поток может выполняться в данный момент
      \item всегда выполняется поток с наивысшим приоритетом
      \item поток работает, пока не блокируется или завершается
    \end{itemize}
  \textbf{Алгоритмы диспетчеризации:}
    \begin{itemize}
      \item карусельного типа (Round Robin)
      \item очередь (FIFO)
    \end{itemize}

  Программист может назначить потоку вручную приоритет и алгоритм
  диспетчеризации, которому тот будет подчиняться.
}
\end{frame}

\begin{frame}
\frametitle{Действия ядра}
\Large{
\begin{enumerate}
  \item Найти потоки, готовые к выполнению.
  \item Если таковые есть, выяснить, возможно ли запустить
    их на процессоре.
  \item Сохранить контекст текущего активного потока.
  \item Загрузить контекст нового потока.
\end{enumerate}
}
\end{frame}

\begin{frame}
\frametitle{FIFO и RR алгоритмы}
\end{frame}

\end{document} % конец документа
